1. Field of the Invention
The present invention relates to a decoder and a decoding method, and more particularly to a decoder and a decoding method both of which decode a block code as an error correction code.
2. Description of the Related Art
A conventional method for decoding a block code as an error correction code is generally comprised of steps of calculating a syndrome from a received coded word, acquiring an erroneous position polynomial from the syndrome, and acquiring an erroneous position of the received coded word by solving the erroneous position polynomial, thereby carrying out an error correction.
For instance, Japanese Unexamined Patent Publications Nos. 10-229342 and 6-276106 suggest a method of correcting an error generated in a transmission path by reversing a bit located in an erroneous position, if such an erroneous position can be found.
As an alternative, as suggested in Japanese Unexamined Patent Publications Nos. 10-256919 and 10-13251, an erroneous position may be identified by defining a conversion table from a syndrome, instead of solving the erroneous position polynomial.
Japanese Unexamined Patent Publication No. 1-240032 has suggested a system of encoding a KL conversion coefficient obtained by KL-converting a vectorial input signal, including first means of determining an auto-correlation coefficient of the input signal, a matrix code book used for KL conversion and defined by inherent vectors of an auto-correlation matrix which is predetermined based on training input signals, an inherent value table associated with the code book, an auto-correlation coefficient table and a table for optimally distributing bits, second means for calculating deformation of a representative vector, based on the auto-correlation coefficient, a representative vector of the matrix code book, the inherent value table, and the auto-correlation coefficient table, retrieving an optimal representative vector to minimize the deformation, third means for conducting KL conversion to the input signal in accordance with the optimal representative vector, fourth means for encoding a conversion coefficient obtained by conversion conducted by the third means, and fifth means for encoding the number of the optimal representative vector.
Japanese Unexamined Patent Publication No. 9-306102 has suggested a digital signal decoder including an equalizer for equalizing a reproduced signal obtained by digitizing an input analog signal indicative of encoded binary data, in accordance with a partial response process, and a decoder which decodes the thus equalized reproduced signal. The equalizer is comprised of an input layer, an output layer, and at least one intermediate layer sandwiched between the input and output layers, and it performs non-linear equalization. The intermediate layer is comprised of a plurality of calculators. At least a part of parameters to be determined for at least one of the input layer, the output layer and the intermediate layer is set at a fixed value.
Japanese Unexamined Patent Publication No. 11-126096 has suggested a voice encoding and decoding apparatus including (a) a filter having a filter coefficient obtained by analyzing and quantizing an adaptive vector indicative of a pitch, a noise vector indicative of noises, and input voice signals, and (b) a distortion calculator which calculates distortion in both the input voice signal and a synthesized voice signal obtained by driving the filter, and identifies one adaptive vector and one noise vector which minimize the distortion. The distortion calculator is designed to have functions of (a) defining a matrix N by calculating both power of a signal generated by synthesizing the adaptive vectors in the filter, and an auto-correlation matrix of a filter coefficient of the filter, and multiplying each components of the auto-correlation matrix with the power, (b) defining a matrix M by synthesizing signals generated by synthesizing the adaptive vectors in the filter, in time inverse order, and calculating an outer product of the thus synthesized signals, (c) subtracting the matrix M from the matrix N to define a matrix L, and (d) calculating the distortion based on the matrix L.
However, the above-mentioned conventional methods are accompanied with a problem that since a syndrome or a solution of an erroneous position polynomial cannot be instantaneously calculated from a received coded word, it is necessary to delay the received coded word by a time necessary for calculating the erroneous position, and as a result, a delay occurs in decoding a block code.
Furthermore, in accordance with the above-mentioned conventional method for acquiring an erroneous position through the use of a conversion table made from a syndrome, it is not necessary to solve an erroneous position polynomial, but instead it is necessary to prepare the conversion table in correspondence to all of the received coded words. For instance, since a Reed-Solomon code in ETSI standards has a coding ratio (204, 188), a potential number of different received coded words is (8xc3x97204)-th power of 2 (288xc3x97204). Thus, the conventional method is accompanied with a problem that the conversion table to be made by hardware/software is unrealizable.
In view of the above-mentioned problems in the conventional methods, it is an object of the present invention to provide a decoder and a decoding method both of which are capable of obtaining an ex-coded word without calculating a syndrome and solving an erroneous position polynomial, and minimizing a decoding delay.
Furthermore, it is another object of the present invention to provide an apparatus for learning a correlation matrix and a method of doing the same, both of which are capable of providing a correlation matrix which can be applied to any polynomial for encoding a word, in order to have a correlation matrix by learning block-encoded words and ex-code words.
In one aspect of the present invention, a decoder for decoding an encoded word X having N bits as an encoded signal which was encoded by an encoder from an ex-code word Y having M bits as a signal before being encoded by the encoder, includes (a) a correlation matrix computation part which makes computation of the encoded word X with a correlation matrix W defined by N rows and M columns, to output a computation result having 1 row and M columns, (b) a judgment part which judges each component in the computation result, and (c) an ex-code word output part which outputs a result of judgment carried out the judgment part, as a recovered ex-code word corresponding to the ex-code word Y.
It is preferable that the correlation matrix computation part computes a product of the encoded word X and the correlation matrix W.
It is preferable that the correlation matrix computation part is comprised of (a1) a memory which stores the correlation matrix W therein, and (a2) a calculator which calculates a product of the encoded word X and the correlation matrix W.
It is preferable that the judgment part transmits a signal of xe2x80x9c1xe2x80x9d if the respective component of the computation result is positive or zero, and transmits a signal of xe2x80x9c0xe2x80x9d if the respective component of the computation result is negative.
It is preferable that the correlation matrix W is defined such that the respective component of the computation result is equal to or greater than a predetermined positive threshold if a corresponding component of the ex-code word Y is 1, and the respective component of the computation result is equal to or smaller than a predetermined negative threshold if a corresponding component of the ex-code word Y is 0.
For instance, the encoded word X may be comprised of symbols. For instance, the encoded word X is comprised of Reed-Solomon codes.
In another aspect of the present invention, there is provided an apparatus for determining a correlation matrix W used in the decoder defined in claim 1, including (a) a correlation matrix calculation part which makes calculation of the encoded word X with the correlation matrix W to a output calculation result, and (b) a device which compares the calculation result to a threshold xc2x1TH determined in accordance with xe2x80x9c1xe2x80x9d or xe2x80x9c1xe2x80x9d as components of the ex-code word Y for each component of the calculation result, and updates the correlation matrix W based on a result of comparison.
It is preferable that the device updates each component of the correlation matrix W such that each component of the calculation result is equal to or greater than a predetermined positive threshold, if the ex-code word Y has a corresponding component of 1, and each component of the calculation result is equal to or smaller than a predetermined negative threshold, if the ex-code word Y has a corresponding component of 0.
It is preferable that the device updates each component of the correlation matrix W by xcex94W, which is a value smaller than the predetermined positive threshold.
In still another aspect of the present invention, there is provided a method of decoding an encoded word X having N bits as an encoded signal that was encoded by an encoder from an ex-code word Y having M bits as a signal before being encoded by the encoder, including the steps of (a) making computation of the encoded word X with a correlation matrix W defined by N rows and M columns, to output a computation result having 1 row and M columns to thereby have M components, (b) judging each component in the computation result, and (c) outputting a result of judgment carried out in the step (b), as a recovered ex-code word corresponding to the ex-code word Y.
It is preferable that a product of the encoded word X and the correlation matrix W is computed in the step (a).
It is preferable that, in the step (b), a signal of xe2x80x9c1xe2x80x9d is transmitted if the respective component of the computation result is positive or zero, and a signal of xe2x80x9c0xe2x80x9d is transmitted if the respective component of the computation result is negative.
It is preferable that the correlation matrix W used in the step (a) is defined such that the respective component of the computation result is equal to or greater than a predetermined positive threshold if a corresponding component of the ex-code word Y is 1, and the respective component of the computation result is equal to or smaller than a predetermined negative threshold if a corresponding component of the ex-code word Y is 0.
There is further provided a method of determining a correlation matrix W used in the method defined in claim 11, including the steps of (a) making calculation of the encoded word X with the correlation matrix W to output a calculation result, (b) comparing the calculation result to the ex-code word Y for each component, and (c) updating the correlation matrix W, based on a result of comparison carried out in the step (b).
It is preferable that each component of the correlation matrix W is updated in the step (c) such that each component of the calculation result is equal to or greater than a predetermined positive threshold if the ex-code word Y has a corresponding component of 1, and each component of the calculation result is equal to or smaller than a predetermined negative threshold if the ex-code word Y has a corresponding component of 0.
It is preferable that each component of the correlation matrix W is updated in the step (c) by xcex94W, which is a value smaller than the predetermined positive threshold.
In yet another aspect of the present invention, there is provided a recording medium readable by a computer, storing a program therein for causing a computer to act as the above-mentioned decoder.
There is further provided a recording medium readable by a computer, storing a program therein for causing a computer to act as the above-mentioned apparatus.
There is still further provided a recording medium readable by a computer, storing a program therein for causing a computer to carry out the above-mentioned method of decoding an encoded word X having N bits as an encoded signal to thereby have an ex-code word Y having M bits as a signal before being encoded.
There is yet further provided a recording medium readable by a computer, storing a program therein for causing a computer to carry out the above-mentioned method of determining a correlation matrix W used in the method of decoding an encoded word X having N bits as an encoded signal to thereby have an ex-code word Y having M bits as a signal before being encoded.
There is further provided a decoder for decoding an encoded word X having N bits as an encoded signal which was encoded by an encoder from an ex-code word Y having M bits as a signal before being encoded by the encoder, including (a) a correlation matrix computation part which makes computation of the encoded word X with a correlation matrix W defined by N rows and M columns, to output a computation result having 1 row and M columns to thereby have M components, (b) a judgment part which judges each component in the computation result, (c) an ex-code word output part which outputs a result of judgment carried out by the judgment part, as a recovered ex-code word corresponding to the ex-code word Y, and (d) a device for determining the correlation matrix W, the device including (d1) a correlation matrix calculation part which makes calculation of the encoded word X with the correlation matrix W to output a calculation result, and (d2) a device which compares the calculation result to the ex-code word Y for each component, and updates the correlation matrix W, based on a result of comparison.
There is further provided a method of decoding an encoded word X having N bits as an encoded signal which was encoded by an encoder from an ex-code word Y having M bits as a signal before being encoded by the encoder, including the steps of (a) determining a correlation matrix W, (b) making computation of the encoded word X with the correlation matrix W defined by N rows and M columns, to output a computation result having 1 row and M columns to thereby have M components, (c) judging each component in the computation result, and (d) outputting a result of judgment carried out in the step (b), as a recovered ex-code word corresponding to the ex-code word Y, the step (a) including the steps of (a1) making calculation of the encoded word X with the correlation matrix W to output a calculation result having M components, (a2) comparing the calculation result to the ex-code word Y for each component, and (a3) updating the correlation matrix W, based on a result of comparison carried out in the step (a2).
The advantages obtained by the aforementioned present invention will be described hereinbelow.
In accordance with the present invention, matrix computation of the correlation matrix W and the block-encoded word X is carried out through the use of the correlation matrix W defined by the block-encoded words X and the ex-codes Y without carrying out computation of a syndrome and without having to solve for an erroneous position polynomial, and each bit in the computation result xe2x80x9cyxe2x80x9d is judged whether it is xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d, thereby the ex-code word Y can be obtained. The embodiment provides an advantage that signal delay is minimized.
In addition, the present invention further provides an advantage that since the correlation matrix W is learnt for updating, based on the block-encoded words X and ex-code words Y, the resulting correlation matrix W can correspond to any polynomial for encoding.
The above and other objects and advantageous features of the present invention will be made apparent from the following description made with reference to the accompanying drawings, in which like reference characters designate the same or similar parts throughout the drawings.